package advance.day01;

/**
 * 描述：
 *      给一个字符串的后面添加最少的字符串让整个字符串形成一个回文字符串
 * @author hl
 * @version 1.0
 * @date 2020/11/4 15:26
 */
public class ManacherShortEnd {
    public static char[] manacherString(String str){
        char[] chs = str.toCharArray();
        char[] res = new char[chs.length * 2 + 1];
        int index = 0;
        for (int i = 0; i < res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : chs[index++];
        }
        return res;
    }
    public static String shortestEnd(String str){
        if (str == null || str.length() == 0) {
            return null;
        }
        char[] chs = manacherString(str);
        int[] pArr = new int[chs.length];
        int r = -1;
        int index = -1;
        int maxContainsEnd = 0;
        for (int i = 0; i < chs.length; i++) {
            pArr[i] = r > i ? Math.min(pArr[2 * index - i], r - i) : 1;
            while(i + pArr[i] < chs.length && i - pArr[i] > -1){
                if (chs[i + pArr[i]] == chs[i - pArr[i]]) {
                    pArr[i]++;
                }else {
                    break;
                }
            }
            if (i + pArr[i] > r) {
                r = i + pArr[i];
                index = i;
            }
            if (r == chs.length) {
                maxContainsEnd = pArr[i];
                break;
            }
        }
        char[] res = new char[str.length() - maxContainsEnd + 1];
        for (int i = 0; i < res.length; i++) {
            res[res.length - 1 - i] = chs[2 * i + 1];
        }
        return new String(res);
    }
    public static void main(String[] args) {
        String str2 = "abcd123321";
        System.out.println(shortestEnd(str2));
    }
}
